package OneDay;
import java.util.*;

public class JZ7 {
        public static TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
            int n = pre.length;
            int m = vin.length;
            if(n == 0 || m == 0) return null;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = new TreeNode(pre[0]);
            TreeNode cur = node;

            for(int i = 1, j = 0; i < n; i++){
                if(cur.val != vin[j]){
                    cur.left = new TreeNode(pre[i]);
                    stack.push(cur);
                    cur = cur.left;
                }else{
                    j++;
                    while(!stack.isEmpty() && stack.peek().val == vin[j]){
                        cur = stack.pop();
                        j++;
                    }
                    cur.right = new TreeNode(pre[i]);
                    cur = cur.right;
                }
            }
            return node;
        }

    public static void main(String[] args) {
        int[] pre =  {1,2,4,7,3,5,6,8};
        int[] vin =  {4,7,2,1,5,3,8,6};
        reConstructBinaryTree(pre,vin);
    }
}
